/*
  Copyright (C) 2011, Kyungjoo Kim
  
  This file is part of LINAL (LINear ALgebra)
  
  All rights reserved.

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.
  
  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Lesser General Public License for more details.
  
  You should have received a copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  Also add information on how to contact you by electronic and paper mail.
  
  
  Kyungjoo Kim
  iamkyungjoo@gmail.com
*/

#ifndef LINAL_DEVICE_CACHE_HXX
#define LINAL_DEVICE_CACHE_HXX

#define LINAL_DEVICE_CACHE_MIN_ITEM 3

namespace linal    {

  typedef class Key_*      Key;

  // Key_ class is used to unique key in cache.
  class Key_ : public Disp_ {
  private:
  protected:
    Int_ _offm, _offn;
    Long_ _buffer;
  public:
    Key_() : _offm(0), _offn(0), _buffer(0) { }
    Key_(Int_ offm, Int_ offn, void *buffer) : _offm(offm), _offn(offn),
                                               _buffer((Long_)buffer) { }
    Key_(FLA_Obj A) : _offm(A.offm), _offn(A.offn),
                      _buffer((Long_)FLA_Obj_buffer_at_view(A)) { }
        
    virtual ~Key_() { }

    virtual std::ostream& content(std::ostream& os) const {
      return (os << "(" << _offm << ", " << _offn << ", " << _buffer << ")");
    }
        
    inline bool operator<(const Key_ &b) const {
      if (_offm   - b._offm  ) return ((_offm   - b._offm  ) < 0);
      if (_offn   - b._offn  ) return ((_offn   - b._offn  ) < 0);
      if (_buffer - b._buffer) return ((_buffer - b._buffer) < 0);
      return false;
    }
    inline bool operator==(const Key_ &b) const {
      return ((_offm == b._offm) && (_offn == b._offn) && (_buffer == b._buffer));
    }
    inline bool operator!=(const Key_ &b) const {
      return !((*this) == b);
    }
  };

  // Cache class exploit software cache in GPU or other devices.
  // Host device does not need.
  template<class Obj_>  
  class Cache_  {
  private:
  protected:
    
    // containers for the matrix objects
    std::vector< Obj_ > _bin, _work;

    // ** trace the cache
    // _dirt  : a deque of dirty matrices in bin
    // _table : a map to clean matrices in bin
    std::vector< std::pair<Int_,std::map<Key_,Int_>::iterator> > _dirt;
    Int_ _dirt_front;

    std::map< Key_, Int_ > _table;
    std::map< Key_, Int_ >::iterator _dummy_in_table;

    inline Int_  _get_dirt_front()  { return _dirt_front; }
    inline Int_  _move_dirt_front() { 
      _dirt_front = ((++_dirt_front)%_dirt.size());
      return _dirt_front;
    }
    inline Int_  _get_n_bin () { return _bin.size(); }
    inline Int_  _get_n_work() { return _work.size(); }

    inline Obj_& _get_obj_from_bin (Int_ index) { return _bin.at(index); }
    inline Obj_& _get_obj_from_work(Int_ index) { return _work.at(index); }

    inline bool _is_in_use(Int_ index) {
      return _get_obj_from_bin(index).is_in_use();
    }

  public:
    Cache_() : _dirt_front(0) { }
    virtual ~Cache_() { }
    /*
    inline virtual std::ostream& content(std::ostream& os) const {
      return ( os  << "- Cache bin("   << _bin.size() 
               << "), work("       << _work.size() 
               << "), dirt("       << _dirt.size()
               << "), dirt_front(" << _dirt_front 
               << ")\n" );
    }
    */
    inline virtual std::ostream& table(std::ostream& os) const {
      std::map< Key_, Int_ >::const_iterator it;
      for (it=_table.begin();it!=_table.end();++it)
        os << (*it).first << "->" << (*it).second << std::endl;
    }
    inline virtual std::ostream& dirt(std::ostream& os) const {
      for (Int_ i=0;i<_dirt_front;++i)
        os << "id " << _dirt.at(i).first 
           << "   " << _dirt.at(i).second->first
           << " " << _dirt.at(i).second->second 
           <<  std::endl;
    }
    
    /*! Initialization
      \param n_bin  [in] workspace for items which needs to stay long
      \param n_work [in] workspace for items which are often refreshed
    */
    inline virtual void initialize(Int_ n_bin, Int_ n_work) { 

      // ** check input 
      // # of item in bin and workspace should be greater than minimum
      n_bin  = ( n_bin  > LINAL_DEVICE_CACHE_MIN_ITEM ? 
                 n_bin  : LINAL_DEVICE_CACHE_MIN_ITEM  );
      n_work = ( n_work > LINAL_DEVICE_CACHE_MIN_ITEM ? 
                 n_work : LINAL_DEVICE_CACHE_MIN_ITEM  );

      //** clear the bin and workspace
      _bin.clear();
      _work.clear();

      // ** initialize the workspace and bin
      Obj_ in;

      for (Int_ i=0;i<n_bin;++i)
        _bin.push_back( in );
        
      for (Int_ i=0;i<n_work;++i)
        _work.push_back( in );

      _table.clear();
      _dirt.clear();

      std::pair< std::map< Key_, Int_ >::iterator, bool >
        ret = _table.insert( std::make_pair( Key_(-1, -1, 0), -1) );

      LINAL_ERROR(ret.second == true,
                  ">> Dummy object exists in the table");

      _dummy_in_table = ret.first;

      // ** matrices in bin are now dirty with dummy iterator
      for (Int_ i=0;i<n_bin;++i)
        _dirt.push_back( std::make_pair(i, _dummy_in_table) );

      _dirt_front = 0;
    }
    
    /*! Finalization
     */
    inline virtual void finalize() {
        
      _bin.clear();
      _work.clear();

      _dirt.clear();
      _table.clear();
    }

    /*! Create matrices
      \param type [in] datatype of matrix
      \param m    [in] length of matrix
      \param n    [in] width of matrix
    */
    inline virtual void create_obj( Int_ type, Int_ m, Int_ n ) {
      for (Int_ i=0;i<_bin.size();++i)
        _bin.at(i).create( type, m, n );

      for (Int_ i=0;i<_work.size();++i)
        _work.at(i).create( type, m, n );
    }
    
    /*! Free the matrices in the bin and work
     */
    inline virtual void free_obj() {
      for (Int_ i=0;i<_bin.size();++i)
        _bin.at(i).free();

      for (Int_ i=0;i<_work.size();++i)
        _work.at(i).free();
    }

    /*! Flush the matrices - Get all matrices dirty
     */
    inline virtual void flush() {
      for (Int_ i=0;i<_bin.size();++i)
        _bin.at(i).set_dirt(true);
    }

    /*! Pre-Sync the object. Function just set up the given matrix dirty. 
      No data transfer involves.
      \param A [in] FLA_Obj
    */
    inline virtual void pre_sync_obj_in_bin(FLA_Obj A) {
      std::map<Key_,Int_>::iterator it = _table.find( Key_(A) );
      if (it != _table.end())
        _get_obj_from_bin(it->second).set_dirt(true);
    }

    /*! Post-Sync the object. Buffer in A is over-written to device cache.
      Data transfer involves.
      \param A [in] FLA_Obj
    */
    inline virtual void post_sync_obj_in_bin(FLA_Obj A, Int_ &cache_hit) {
      std::map<Key_,Int_>::iterator it = _table.find( Key_(A) );
      if (it != _table.end()) {
        Obj_ &AA = _get_obj_from_bin(it->second);

        if (!AA.is_dirty()) {
          Obj_ A_device;
          AA.extract( A_device, A.m, A.n );
          A_device.set_matrix_from( A, cache_hit );
        }
      }
    }

    /*! Pull out the object in the cache. 
      \param A [in] FLA_Obj
    */
    inline virtual Obj_* pull_obj_from_bin(FLA_Obj A) {
      // ** Search the table first
      std::pair< Key_, Int_ > in = std::make_pair( Key_(A), -1 );
      std::pair< std::map<Key_,Int_>::iterator , bool > ret;

      Int_ index, front;
      bool is_dirt;

      {
        ret = _table.insert( in );
        if (ret.second) {

          // There is NOT existing item on the table
          Int_ start = _get_dirt_front();
          do {
            front   = _get_dirt_front();
            index   = _dirt.at(front).first;
            LINAL_ERROR(start != _move_dirt_front(),
                        ">> Cache is too small. Increase the cache size");
          } while ( _is_in_use(index) );

          // If dirt is connected to map, update the map
          if (_dirt.at(front).second != _dummy_in_table)
            _table.erase( _dirt.at(front).second );

          _dirt.at(front).second = ret.first;
          ret.first->second = index;

          is_dirt = true;

        } else {

          // There is an existing item on the table
          index   = ret.first->second;
          is_dirt = false;

        }
      }

      Obj_ &obj = _get_obj_from_bin(index);

      if (is_dirt) obj.set_dirt(is_dirt);
      obj.set_use (true);

      return &obj;
    }

    /*! Pull out the object from the workspace
      \param index [in] location of the object in workspace
    */
    inline virtual Obj_* pull_obj_from_work(Int_ index) {
      // ** Matrices from work bin are always dirty
      Obj_ &obj = _get_obj_from_work(index);
      obj.set_dirt(true);
      obj.set_use (true);

      return &obj;
    }

  };
}

#endif
